package 链表;

public class _206_反转链表 {

    //递归
    public ListNode reverseList(ListNode head) {
        /**
         *         if (head == null || head.next == null) return head;
         *                 ListNode newHead = reverseList(head.next);
         *                         head.next.next = head;
         *                                 head.next = null;
         *                                         return newHead;*/
        /*否则空指针异常*/
        //链表空的，head是空的
        //只有一个head，只有一个节点
        if (head == null || head.next == null) return head;
        //加入head是5，则head.next是4，
        //如果函数实现了，说明1-2-3-4是实现了的，返回了的，那么就还剩下head（5）这个node没有处理
        //newHead就是已经处理好的，1-2-3-4
		//等到这句话执行完了，下面的才会去执行，也就是1-2-3-4已经反转好了
        ListNode newHead = reverseList(head.next);
        //让4指向5，4-》5；head.next是4，4.next指向5，5指向null
        // head.next.next指向；head4指向5
        head.next.next = head;
        //5.next就是指向空，结束了
        head.next = null;
        return newHead;
    }


    /*非递归、迭代*/
    public ListNode reverseList2(ListNode head) {
        //否则空指针异常
        if (head == null || head.next == null) return head;
        ListNode newHead = null;
        while (head != null) {
            //head的下一个节点给tmp暂存
            ListNode tmp = head.next;
            //head的下一个节点，指向newhead
            head.next = newHead;
            //head给到newhead，（也就是head.next指向head，反过来了）
            //本来是head->head.next，现在反过来了，
            newHead = head;
            //head是head.next，
            head = tmp;
        }

        return newHead;
    }

}